package study.datastructure.order.sort;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2024-07-09 16:43
 */

import java.util.Arrays;

/**
 2024/7/9,
 */

//直接插入排序
public class InsertionSort {
    public static void insertionSort(int[] array) {
        int n=array.length;
        for (int i = 1; i < n; i++) {
            int key=array[i];
            int j=i-1;

            //将array[i] 插入到0 ...i-1 中
            while (j>=0 && array[j]>key){
                array[j+1]= array[j];
                j=j-1;
            }
            array[j+1]=key;
        }

    }

    public static void main(String[] args) {
        int[] arr = {10, 3, 7, 1, 9, 6};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

}
